package com.kaifamiao.exercises.queue;


public class KaifamiaoQueue<E> {

    private Node<E> first; // 第一个节点
    private Node<E> last; // 最后一个节点
    private int count; // 用于统计元素个数

    /**
     * 根据指定索引获取相应的元素
     * @param index 表示索引(索引值从零开始)
     * @return
     */
    public E get( int index ) {

        return null;
    }

    /**
     * 用指定的对象(item)替换指定位置(index)的元素
     * @param index 表示需要替换的元素位置
     * @param item 替换后的元素
     * @return 返回index处原来的元素
     */
    public E set( int index , E item ) {
        return null;
    }

    /**
     * 在指定位置(index)插入指定的对象(item)
     * @param index 需要插入新元素的位置
     * @param item 被插入的新元素
     */
    public void add( int index , E item ) {

    }

    /**
     * 向队列尾部追加元素
     * @param item 被追加的元素
     */
    public void offer( E item ) {
        // 根据用户传入的参数创建一个Node实例
        Node<E> node = new Node<>( last , item, null );
        // 若 链表 为空 (即首个节点为 null)
        if( first == null ) {
            first = node; // 以node为首节点
            last = node; // 以node为尾节点
        }
        // 若 链表中 只有一个节点 (即首节点和尾节点是同一个对象)
        else if ( last == first ){
            last = node; // 以node为尾节点
            first.next = node; // 让首节点next指针指向node
        }
        // 若 链表有多个节点 ( 大于等于 2 )
        else {
            last.next = node; // 让曾经的尾节点的next指针指向node
            last = node ; // 以node为尾节点
        }
        // 让元素计数器增加
        this.count++;
    }

    /**
     * 删除并返回队列头部元素
     * @return 返回队列头部元素
     */
    public E poll(){
        if( first == null ) {
            return null;
        }

        E item = first.item;

        if( first == last ) {
            first = null;
            last = null;
        } else {
            first = first.next;
            first.previous = null;
        }

        count--;
        return item;
    }

    /**
     * 检查队列头部元素(但不删除队列头部元素)
     * @return 返回队列头部元素
     */
    public E peek(){
        return first == null ? null : first.item;
    }

    /**
     * 获取队列中的元素个数
     * @return 返回队列中的元素个数
     */
    public int size(){
        return count;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return count == 0 ;
    }

    /**
     * 通过重写从Object继承的toString方法返回当前 Queue实例的 字符串形式
     * @return
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append('[');
        if( first == last ) {
            builder.append( first == null ? "" : first.toString() );
        } else {
            // 从头到尾遍历链表，将每个节点（Node）的 item 连接到一个字符串中
            Node<E> node = first;
            while ( node != null) {
                builder.append( node.toString() );
                builder.append( ',' );
                node = node.next;
            }
            int index = builder.lastIndexOf( "," );
            if( index != -1 ) {
                builder.deleteCharAt( index );
            }
        }
        builder.append(']');
        return builder.toString();
    }

    private static class Node<E> {
        E item; // 当前节点存储的数据
        Node<E> previous; // 指向前驱节点
        Node<E> next; // 指向后继节点
        public Node(Node<E> previous, E item, Node<E> next) {
            this.previous = previous;
            this.item = item;
            this.next = next;
        }
        @Override
        public String toString() {
            return item == null ? "null" : item.toString();
        }
    }
}
